#include<vector>
using namespace std;
class Solution {
private:
    bool search(const vector<int>& nums, int target, int start,int end) {
        if (start == end) return false;
        if (start == end - 1)
            return nums[start] == target;
        int mid = start + (end - start) / 2;
        if (nums[mid] > target) return search(nums, target, start, mid);
        if (nums[mid] < target) return search(nums, target, mid + 1, end);
        return true;
    }

    bool search(const vector<vector<int>>& matrix, int target,int row1,int row2) {
        if (matrix[row1][0] > target || matrix[row2][matrix[row2].size()-1] < target)
            return false;
        if (row1 == row2)
            return search(matrix[row1], target, 0, matrix[row1].size());
        int mid = row1 + (row2 - row1) / 2;
        if (matrix[mid][0] > target)
            return search(matrix, target, row1, mid - 1);
        if (matrix[mid][matrix[mid].size() - 1] < target)
            return search(matrix, target, mid + 1, row2);
        return search(matrix[mid], target, 0, matrix[mid].size());
    }


public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0|| matrix[0].size()==0)
            return false;
        return search(matrix, target, 0, matrix.size() - 1);
    }
};